#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_FLIGHTS 100
#define MAX_AIRPORTS 20
#define MAX_CODE_LEN 16
#define HASH_SIZE 103

// 航班结构体
typedef struct Flight {
    char flight_no[MAX_CODE_LEN];
    char from[MAX_CODE_LEN];
    char to[MAX_CODE_LEN];
    char depart_time[20];
    char arrive_time[20];
    int seats;
    struct Flight* next; // 用于链表
} Flight;

// 1. 数组存储航班信息
Flight flight_array[MAX_FLIGHTS];
int flight_count = 0;

// 2. 链表存储航班信息
Flight* flight_list = NULL;

// 3. 图结构（邻接表）存储航线网络
typedef struct Edge {
    int to; // 目的机场在airports数组中的下标
    struct Edge* next;
} Edge;

typedef struct {
    char code[MAX_CODE_LEN]; // 机场代码
    Edge* adj;               // 邻接表
} Airport;

Airport airports[MAX_AIRPORTS];
int airport_count = 0;

// 4. 二叉排序树
typedef struct BSTNode {
    Flight* flight;
    struct BSTNode* left, *right;
} BSTNode;
BSTNode* bst_root = NULL;

// 5. 开放地址哈希表
Flight* hash_table_open[HASH_SIZE];

// 6. 链地址哈希表
typedef struct HashNode {
    Flight* flight;
    struct HashNode* next;
} HashNode;
HashNode* hash_table_chain[HASH_SIZE];

// 哈希函数
unsigned int hash_flight_no(const char* s) {
    unsigned int h = 0;
    while (*s) h = h * 131 + *s++;
    return h % HASH_SIZE;
}

// 添加机场，返回下标
int add_airport(const char* code) {
    for (int i = 0; i < airport_count; i++)
        if (strcmp(airports[i].code, code) == 0)
            return i;
    strcpy(airports[airport_count].code, code);
    airports[airport_count].adj = NULL;
    return airport_count++;
}

// 添加航班到数组、链表、图
void add_flight(const Flight* f) {
    // 数组
    flight_array[flight_count++] = *f;

    // 链表
    Flight* node = (Flight*)malloc(sizeof(Flight));
    *node = *f;
    node->next = flight_list;
    flight_list = node;

    // 图
    int from_idx = add_airport(f->from);
    int to_idx = add_airport(f->to);
    Edge* e = (Edge*)malloc(sizeof(Edge));
    e->to = to_idx;
    e->next = airports[from_idx].adj;
    airports[from_idx].adj = e;
}

// 读取CSV文件
void load_flights_csv(const char* filename) {
    FILE* fp = fopen(filename, "r");
    if (!fp) { printf("无法打开文件\n"); exit(1); }
    char line[256];
    while (fgets(line, sizeof(line), fp)) {
        Flight f;
        sscanf(line, "%[^,],%[^,],%[^,],%[^,],%[^,],%d",
            f.flight_no, f.from, f.to, f.depart_time, f.arrive_time, &f.seats);
        add_flight(&f);
    }
    fclose(fp);
}

// 顺序查找（数组）
Flight* seq_search_array(const char* flight_no) {
    for (int i = 0; i < flight_count; i++)
        if (strcmp(flight_array[i].flight_no, flight_no) == 0)
            return &flight_array[i];
    return NULL;
}

// 顺序查找（链表）
Flight* seq_search_list(const char* flight_no) {
    for (Flight* p = flight_list; p; p = p->next)
        if (strcmp(p->flight_no, flight_no) == 0)
            return p;
    return NULL;
}

// 折半查找（有序数组，需先排序）
int cmp_flight(const void* a, const void* b) {
    return strcmp(((Flight*)a)->flight_no, ((Flight*)b)->flight_no);
}
Flight* bin_search_array(const char* flight_no) {
    int l = 0, r = flight_count - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        int cmp = strcmp(flight_array[m].flight_no, flight_no);
        if (cmp == 0) return &flight_array[m];
        else if (cmp < 0) l = m + 1;
        else r = m - 1;
    }
    return NULL;
}

// 二叉排序树插入
BSTNode* bst_insert(BSTNode* root, Flight* f) {
    if (!root) {
        BSTNode* node = (BSTNode*)malloc(sizeof(BSTNode));
        node->flight = f; node->left = node->right = NULL;
        return node;
    }
    int cmp = strcmp(f->flight_no, root->flight->flight_no);
    if (cmp < 0) root->left = bst_insert(root->left, f);
    else if (cmp > 0) root->right = bst_insert(root->right, f);
    return root;
}
// 二叉排序树查找
Flight* bst_search(BSTNode* root, const char* flight_no) {
    if (!root) return NULL;
    int cmp = strcmp(flight_no, root->flight->flight_no);
    if (cmp == 0) return root->flight;
    else if (cmp < 0) return bst_search(root->left, flight_no);
    else return bst_search(root->right, flight_no);
}

// 开放地址法哈希插入
void hash_open_insert(Flight* f) {
    unsigned int h = hash_flight_no(f->flight_no);
    while (hash_table_open[h]) h = (h + 1) % HASH_SIZE;
    hash_table_open[h] = f;
}
// 开放地址法哈希查找
Flight* hash_open_search(const char* flight_no) {
    unsigned int h = hash_flight_no(flight_no);
    unsigned int start = h;
    while (hash_table_open[h]) {
        if (strcmp(hash_table_open[h]->flight_no, flight_no) == 0)
            return hash_table_open[h];
        h = (h + 1) % HASH_SIZE;
        if (h == start) break;
    }
    return NULL;
}

// 链地址法哈希插入
void hash_chain_insert(Flight* f) {
    unsigned int h = hash_flight_no(f->flight_no);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->flight = f; node->next = hash_table_chain[h]; hash_table_chain[h] = node;
}
// 链地址法哈希查找
Flight* hash_chain_search(const char* flight_no) {
    unsigned int h = hash_flight_no(flight_no);
    for (HashNode* p = hash_table_chain[h]; p; p = p->next)
        if (strcmp(p->flight->flight_no, flight_no) == 0) // 修改此行
            return p->flight;
    return NULL;
}

// 增加航班（直接调用add_flight即可）

// 删除航班（以数组为例，链表和其他结构可类似实现）
int delete_flight(const char* flight_no) {
    int found = 0;
    for (int i = 0; i < flight_count; i++) {
        if (strcmp(flight_array[i].flight_no, flight_no) == 0) {
            found = 1;
            for (int j = i; j < flight_count - 1; j++)
                flight_array[j] = flight_array[j + 1];
            flight_count--;
            break;
        }
    }
    // 链表删除
    Flight **pp = &flight_list, *p = flight_list;
    while (p) {
        if (strcmp(p->flight_no, flight_no) == 0) {
            *pp = p->next;
            free(p);
            break;
        }
        pp = &p->next;
        p = p->next;
    }
    // 其他结构（BST、哈希）可重建
    return found;
}


// 修改航班（以数组为例）
int modify_flight(const char* flight_no, const Flight* newf) {
    for (int i = 0; i < flight_count; i++) {
        if (strcmp(flight_array[i].flight_no, flight_no) == 0) {
            flight_array[i] = *newf;
            return 1;
        }
    }
    return 0;
}

// 打印航班信息
void print_flight(const Flight* f) {
    if (!f) { printf("未找到航班\n"); return; }
    printf("%s: %s->%s %s-%s 座位%d\n", f->flight_no, f->from, f->to, f->depart_time, f->arrive_time, f->seats);
}

// 构建二叉排序树和哈希表
void build_index_structures() {
    bst_root = NULL;
    memset(hash_table_open, 0, sizeof(hash_table_open));
    memset(hash_table_chain, 0, sizeof(hash_table_chain));
    for (int i = 0; i < flight_count; i++) {
        bst_root = bst_insert(bst_root, &flight_array[i]);
        hash_open_insert(&flight_array[i]);
        hash_chain_insert(&flight_array[i]);
    }
}
// 主函数：演示六种查找


void add_flight_to_csv(const char* filename, const Flight* f) {
    FILE* fp = fopen(filename, "a+");
    if (!fp) { printf("无法打开文件写入\n"); return; }
    fseek(fp, 0, SEEK_END);
    long filesize = ftell(fp);
    if (filesize > 0) {
        fseek(fp, -1, SEEK_END);
        char last;
        fread(&last, 1, 1, fp);
        if (last != '\n') {
            fputc('\n', fp);
        }
    }
    fprintf(fp, "%s,%s,%s,%s,%s,%d\n", f->flight_no, f->from, f->to, f->depart_time, f->arrive_time, f->seats);
    fclose(fp);
}

// 删除航班后，重写CSV文件
void rewrite_csv(const char* filename) {
    FILE* fp = fopen(filename, "w");
    if (!fp) { printf("无法打开文件写入\n"); return; }
    for (int i = 0; i < flight_count; i++) {
        Flight* f = &flight_array[i];
        fprintf(fp, "%s,%s,%s,%s,%s,%d\n", f->flight_no, f->from, f->to, f->depart_time, f->arrive_time, f->seats);
    }
    fclose(fp);
}



void clear_flight_list() {
    Flight* p = flight_list;
    while (p) {
        Flight* tmp = p;
        p = p->next;
        free(tmp);
    }
    flight_list = NULL;
}

// 重新加载所有内存数据
void reload_all(const char* csvfile) {
    flight_count = 0;
    airport_count = 0;
    clear_flight_list();
    load_flights_csv(csvfile);
    qsort(flight_array, flight_count, sizeof(Flight), cmp_flight);
    build_index_structures();
}


//=======================================================================
//功能4
// 获取机场下标
int get_airport_idx(const char* code) {
    for (int i = 0; i < airport_count; i++)
        if (strcmp(airports[i].code, code) == 0) return i;
    return -1;
}

// Dijkstra算法
void dijkstra(int src, int* dist, int* prev) {
    int n = airport_count, vis[MAX_AIRPORTS] = {0};
    for (int i = 0; i < n; i++) dist[i] = 1000000, prev[i] = -1;
    dist[src] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, min = 1000000;
        for (int j = 0; j < n; j++)
            if (!vis[j] && dist[j] < min) { min = dist[j]; u = j; }
        if (u == -1) break;
        vis[u] = 1;
        for (Edge* e = airports[u].adj; e; e = e->next)
            if (dist[e->to] > dist[u] + 1) { // 权重为1，表示一条航线
                dist[e->to] = dist[u] + 1;
                prev[e->to] = u;
            }
    }
}
// 输出最短路径
void print_path(int* prev, int src, int dst) {
    int path[MAX_AIRPORTS], len = 0;
    for (int v = dst; v != -1; v = prev[v]) path[len++] = v;
    printf("最短航线：");
    for (int i = len - 1; i >= 0; i--) {
        printf("%s", airports[path[i]].code);
        if (i > 0) printf(" -> ");
    }
    printf("\n");
}


// 查找某一段的航班（只输出第一个匹配的航班）
void print_flight_segment(const char* from, const char* to) {
    for (int i = 0; i < flight_count; i++) {
        if (strcmp(flight_array[i].from, from) == 0 && strcmp(flight_array[i].to, to) == 0) {
            printf("  航班号: %s, %s->%s, %s-%s, 座位%d\n",
                flight_array[i].flight_no, flight_array[i].from, flight_array[i].to,
                flight_array[i].depart_time, flight_array[i].arrive_time, flight_array[i].seats);
            return;
        }
    }
    printf("  无直达航班信息: %s->%s\n", from, to);
}

// 输出最短路径及航班信息
void print_path_with_flights(int* prev, int src, int dst) {
    int path[MAX_AIRPORTS], len = 0;
    for (int v = dst; v != -1; v = prev[v]) path[len++] = v;
    printf("最短航线：");
    for (int i = len - 1; i >= 0; i--) {
        printf("%s", airports[path[i]].code);
        if (i > 0) printf(" -> ");
    }
    printf("\n");
    // 输出每一段的航班
    for (int i = len - 1; i > 0; i--) {
        print_flight_segment(airports[path[i]].code, airports[path[i-1]].code);
    }
}
//=======================================================================

//实现功能5
// 统计某机场起降数量
int stat_airport(const char* code) {
    int cnt = 0;
    for (int i = 0; i < flight_count; i++)
        if (strcmp(flight_array[i].from, code) == 0 || strcmp(flight_array[i].to, code) == 0)
            cnt++;
    return cnt;
}

// 统计热门航线
void stat_hot_routes() {
    int freq[MAX_AIRPORTS][MAX_AIRPORTS] = {0};
    for (int i = 0; i < flight_count; i++) {
        int from = get_airport_idx(flight_array[i].from);
        int to = get_airport_idx(flight_array[i].to);
        if (from >= 0 && to >= 0) freq[from][to]++;
    }
    int max = 0;
    for (int i = 0; i < airport_count; i++)
        for (int j = 0; j < airport_count; j++)
            if (freq[i][j] > max) max = freq[i][j];
    if (max == 0) {
        printf("无热门航线数据\n");
        return;
    }
    printf("热门航线：\n");
    for (int i = 0; i < airport_count; i++) {
        for (int j = 0; j < airport_count; j++) {
            if (freq[i][j] == max) {
                printf("%s -> %s，航班数：%d\n", airports[i].code, airports[j].code, max);
            }
        }
    }
}

// 计算ASL（以顺序查找为例）
double calc_asl_seq_array() {
    double sum = 0;
    for (int i = 0; i < flight_count; i++) {
        int steps = 1;
        for (int j = 0; j < flight_count; j++) {
            if (strcmp(flight_array[j].flight_no, flight_array[i].flight_no) == 0)
                break;
            steps++;
        }
        sum += steps;
    }
    return sum / flight_count;
}
double calc_asl_bin_array() {
    double sum = 0;
    for (int i = 0; i < flight_count; i++) {
        int l = 0, r = flight_count - 1, steps = 1;
        while (l <= r) {
            int m = (l + r) / 2;
            int cmp = strcmp(flight_array[m].flight_no, flight_array[i].flight_no);
            if (cmp == 0) break;
            else if (cmp < 0) l = m + 1;
            else r = m - 1;
            steps++;
        }
        sum += steps;
    }
    return sum / flight_count;
}
// 二叉排序树ASL
void bst_asl_helper(BSTNode* root, int depth, int* total_depth, int* count) {
    if (!root) return;
    *total_depth += depth;
    (*count)++;
    bst_asl_helper(root->left, depth + 1, total_depth, count);
    bst_asl_helper(root->right, depth + 1, total_depth, count);
}
double calc_asl_bst() {
    int total_depth = 0, count = 0;
    bst_asl_helper(bst_root, 1, &total_depth, &count);
    return count ? (double)total_depth / count : 0;
}
// 开放地址哈希ASL
double calc_asl_hash_open() {
    double sum = 0;
    for (int i = 0; i < flight_count; i++) {
        unsigned int h = hash_flight_no(flight_array[i].flight_no);
        int steps = 1;
        unsigned int start = h;
        while (hash_table_open[h]) {
            if (strcmp(hash_table_open[h]->flight_no, flight_array[i].flight_no) == 0)
                break;
            h = (h + 1) % HASH_SIZE;
            steps++;
            if (h == start) break;
        }
        sum += steps;
    }
    return sum / flight_count;
}
// 链地址哈希ASL
double calc_asl_hash_chain() {
    double sum = 0;
    for (int i = 0; i < flight_count; i++) {
        unsigned int h = hash_flight_no(flight_array[i].flight_no);
        int steps = 1;
        for (HashNode* p = hash_table_chain[h]; p; p = p->next) {
            if (strcmp(p->flight->flight_no, flight_array[i].flight_no) == 0)
                break;
            steps++;
        }
        sum += steps;
    }
    return sum / flight_count;
}
double calc_asl_seq_list() {
    double sum = 0;
    for (int i = 0; i < flight_count; i++) {
        int steps = 1;
        for (Flight* p = flight_list; p; p = p->next) {
            if (strcmp(p->flight_no, flight_array[i].flight_no) == 0)
                break;
            steps++;
        }
        sum += steps;
    }
    return sum / flight_count;
}
//========================================================================
int main() {
    const char* csvfile = "d:\\vscode-index\\zy\\11.csv";
    reload_all(csvfile);

    int choice;
    while (1) {
        printf("\n请选择操作：\n");
        printf("1. 查找航班号\n");
        printf("2. 增加航班\n");
        printf("3. 删除航班\n");
        printf("4. 航线规划（最短航线）\n");
        printf("5. 起降数量及热门航线\n");
        printf("0. 退出\n");
        printf("输入选项：");
        scanf("%d", &choice);

        if (choice == 0) break;

        if (choice == 1) {
            char key[MAX_CODE_LEN];
            printf("请输入要查找的航班号：");
            scanf("%s", key);
            printf("1. 数组顺序查找：\n");
            print_flight(seq_search_array(key));
            printf("2. 链表顺序查找：\n");
            print_flight(seq_search_list(key));
            printf("3. 有序数组折半查找：\n");
            print_flight(bin_search_array(key));
            printf("4. 二叉排序树查找：\n");
            print_flight(bst_search(bst_root, key));
            printf("5. 开放地址哈希查找：\n");
            print_flight(hash_open_search(key));
            printf("6. 链地址哈希查找：\n");
            print_flight(hash_chain_search(key));
        } else if (choice == 2) {
            Flight newf;
            printf("请输入航班号：");
            scanf("%s", newf.flight_no);
            // 检查是否已存在
            if (seq_search_array(newf.flight_no)) {
                printf("该航班号已存在，不能重复添加！\n");
                continue;
            }
            printf("请输入出发地：");
            scanf("%s", newf.from);
            printf("请输入目的地：");
            scanf("%s", newf.to);
            printf("请输入出发时间：");
            scanf("%s", newf.depart_time);
            printf("请输入到达时间：");
            scanf("%s", newf.arrive_time);
            printf("请输入座位数：");
            scanf("%d", &newf.seats);
            add_flight_to_csv(csvfile, &newf); // 先写入文件
            reload_all(csvfile); // 再重新加载到内存
            printf("航班添加成功！\n");
        } else if (choice == 3) {
            char key[MAX_CODE_LEN];
            printf("请输入要删除的航班号：");
            scanf("%s", key);
            if (delete_flight(key)) {
                rewrite_csv(csvfile); // 先重写文件
                // 清空内存再重新加载，确保不会把旧数据读回来
                reload_all(csvfile);
                printf("航班删除成功！\n");
            } else {
                printf("未找到该航班，删除失败！\n");
            }
        } else if (choice == 4) {
            char src_code[MAX_CODE_LEN], dst_code[MAX_CODE_LEN];
    printf("请输入出发机场代码：");
    scanf("%s", src_code);
    printf("请输入目的机场代码：");
    scanf("%s", dst_code);
    int src = get_airport_idx(src_code);
    int dst = get_airport_idx(dst_code);
    if (src == -1 || dst == -1) {
        printf("机场代码有误！\n");
        continue;
    }
    int dist[MAX_AIRPORTS], prev[MAX_AIRPORTS];
    dijkstra(src, dist, prev);
    if (dist[dst] == 1000000) {
        printf("无可达航线！\n");
    } else {
        printf("最短航线长度：%d\n", dist[dst]);
        print_path_with_flights(prev, src, dst);
    }
        } else if (choice == 5) {
    char code[MAX_CODE_LEN];
    printf("请输入机场代码：");
    scanf("%s", code);
    int cnt = stat_airport(code);
    printf("机场%s起降航班数：%d\n", code, cnt);
    stat_hot_routes();
    printf("数组顺序查找ASL: %.2lf\n", calc_asl_seq_array());
    printf("链表顺序查找ASL: %.2lf\n", calc_asl_seq_list());
    printf("有序数组折半查找ASL: %.2lf\n", calc_asl_bin_array());
    printf("二叉排序树查找ASL: %.2lf\n", calc_asl_bst());
    printf("开放地址哈希查找ASL: %.2lf\n", calc_asl_hash_open());
    printf("链地址哈希查找ASL: %.2lf\n", calc_asl_hash_chain());
    printf("（ASL越小，查找效率越高）\n");
}
        
        
        else {
            printf("无效选项，请重新输入！\n");
        }
    }
    clear_flight_list();
    return 0;
}













// int main() {
//     const char* csvfile = "d:\\vscode-index\\zy\\11.csv";
//     load_flights_csv(csvfile);
//     // 排序用于折半查找
//     qsort(flight_array, flight_count, sizeof(Flight), cmp_flight);
//     build_index_structures();

//     int choice;
//     while (1) {
//         printf("\n请选择操作：\n");
//         printf("1. 查找航班号\n");
//         printf("2. 增加航班\n");
//         printf("3. 删除航班\n");
//         printf("0. 退出\n");
//         printf("输入选项：");
//         scanf("%d", &choice);

//         if (choice == 0) break;

//         if (choice == 1) {
//             char key[MAX_CODE_LEN];
//             printf("请输入要查找的航班号：");
//             scanf("%s", key);
//             printf("1. 数组顺序查找：\n");
//             print_flight(seq_search_array(key));
//             printf("2. 链表顺序查找：\n");
//             print_flight(seq_search_list(key));
//             printf("3. 有序数组折半查找：\n");
//             print_flight(bin_search_array(key));
//             printf("4. 二叉排序树查找：\n");
//             print_flight(bst_search(bst_root, key));
//             printf("5. 开放地址哈希查找：\n");
//             print_flight(hash_open_search(key));
//             printf("6. 链地址哈希查找：\n");
//             print_flight(hash_chain_search(key));
//         } else if (choice == 2) {
//             Flight newf;
//             printf("请输入航班号：");
//             scanf("%s", newf.flight_no);
//             printf("请输入出发地：");
//             scanf("%s", newf.from);
//             printf("请输入目的地：");
//             scanf("%s", newf.to);
//             printf("请输入出发时间：");
//             scanf("%s", newf.depart_time);
//             printf("请输入到达时间：");
//             scanf("%s", newf.arrive_time);
//             printf("请输入座位数：");
//             scanf("%d", &newf.seats);
//             add_flight(&newf);
//             add_flight_to_csv(csvfile, &newf); // 追加到CSV
//             qsort(flight_array, flight_count, sizeof(Flight), cmp_flight);
//             build_index_structures();
//             printf("航班添加成功！\n");
//         } else if (choice == 3) {
//             char key[MAX_CODE_LEN];
//             printf("请输入要删除的航班号：");
//             scanf("%s", key);
//             if (delete_flight(key)) {
//                 qsort(flight_array, flight_count, sizeof(Flight), cmp_flight);
//                 build_index_structures();
//                 rewrite_csv(csvfile); // 删除后重写CSV
//                 printf("航班删除成功！\n");
//             } else {
//                 printf("未找到该航班，删除失败！\n");
//             }
//         } else {
//             printf("无效选项，请重新输入！\n");
//         }
//     }
//     return 0;
// }